// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-28 16:49
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

@SuppressWarnings("ALL")
public class LongestPalindrome {
    // 返回给定字符串中字符所能构建的最长回文串 ==构建==
    public int longestPalindromeT(String s) {
        int n = s.length();
        int ans = 0;
        boolean flag = false;
        if (n == 1) {
            return 1;
        } else if (n == 0) {
            return 0;
        }
        int[] nums = new int[52];
        for (int i = 0; i < n; i++) {
            // 获得字符串中各个字符的个数
            nums[s.charAt(i) - 'A']++;
        }
        // 取出所有偶数字符，再加上一个字符即可
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 2) {
                if (nums[i] % 2 == 1) {
                    flag = true;
                }
                ans += (nums[i]) / 2 * 2;
            } else if (nums[i] == 1) {
                flag = true;
            }
        }
        return flag ? ans + 1 : ans;
    }

    /**
     * 返回给定字符串中最长回文串
     *
     * @param s源字符串
     * @return最长回文字符串
     */
    public String longestPalindromeTT(String s) {
        //  1 暴力方法
        int max = 1, begin = 0, len = s.length();
        if (len < 2) {
            return s;
        }
        char[] chars = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (validPalindprome(chars, i, j) && (j - i + 1) > max) {
                    begin = i;
                    max = j - i + 1;
                }
            }
        }
        return s.substring(begin, begin + max);
    }

    /**
     * 判断区间内字符串是否是回文字符串
     */
    private boolean validPalindprome(char[] chs, int start, int end) {
        while (start <= end) {
            if (chs[start] != chs[end]) {
                return false;
            }
            ++start;
            --end;
        }
        return true;
    }


    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1, begin = 0;
        for (int i = 0; i < n; i++) {
            // 对角线单个字符串一定是回文的
            dp[i][i] = true;
        }
        char[] chars = s.toCharArray();
        for (int j = 1; j < n; j++) {
            // 对上表格的绘制
            for (int i = 0; i < j; i++) {
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (j - i + 1 > maxLen && dp[i][j]) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }

        }
        return s.substring(begin, begin + maxLen);

    }


    /**
     * 中心扩散方法
     */
    public String longestPalindromeM(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        int[] odd = new int[2];
        int[] even = new int[2];
        int[] res = new int[2];
        int[] max = new int[2];
        int maxLen = 0;

        for (int i = 0; i < n - 1; i++) {
            odd = centerSpread(s, i, i);
            even = centerSpread(s, i, i + 1);
            max = odd[1] > even[1] ? odd : even;
            if (max[1] > maxLen) {
                res = max;
                maxLen = max[1];
            }
        }
        return s.substring(res[0], res[0] + res[1]);
    }

    /**
     * 中心扩散获取最长回文串
     */
    private int[] centerSpread(String s, int left, int right) {
        int len = s.length();


        while (left >= 0 && right < len) {
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }
        return new int[]{left + 1, right - left - 1};
    }



    @Test
    public void shout00() {
        String test = "bbb";
        System.out.println(longestPalindrome(test));
    }
}
